// license: http://code.google.com/p/jc-pheap/source/browse/trunk/jc-pheap/license.txt
package persistent_heap.internals;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

/* lisp-like wrapper for functional (non-destructive) setting
 */
class LinkCell<HeapT>
{
   HeapT ptr = null;
}

// overloaded to be nodes, trees and even heaps depending on use.
// 1) the head of the root list is a heap. the sibling is used
// to traverse the root list
// 2) every root is a tree
// 3) everything below the root is a node in a tree, but when it bubbles
// to the top, it becomes an item in the root list
public class LinkedHeap<T extends Comparable<? super T>> //implements Comparable<LinkedHeap<T>>
{
   public T value = null;
   int rank = 0;
   
   //used in root and tree depending on context, we hope
   LinkCell<LinkedHeap<T>> sib = new LinkCell<LinkedHeap<T>>();
   
   LinkCell<LinkedHeap<T>> child = new LinkCell<LinkedHeap<T>>();

   public LinkedHeap(T entry)
   {
      value(entry);
   }
   
   public LinkedHeap<T> insert(T entry)
   {
      LinkedHeap<T> neib = next();
      
      if (neib != null && rank == neib.rank)
      {
         return link(new LinkedHeap<T>(entry), neib);
      }
      
      return link(new LinkedHeap<T>(entry));
   }

   public LinkedHeap<T> findMin()
   {
      LinkedHeap<T> min = this;
      for (LinkedHeap<T> iter = next(); iter != null; iter=iter.next())
      {
         if (iter.lt(min))
         {
            min = iter;
         }
      }

      return min;
   } 
   
   public LinkedHeap<T> meld(LinkedHeap<T> otherHeap)
   {
      if (otherHeap == null)
         return this;

      LinkCell<LinkedHeap<T>> hint = new LinkCell<LinkedHeap<T>>();
      
      for (LinkedHeap<T> iter = this; iter != null; iter=iter.next())
      {
         otherHeap = otherHeap.meldOne(iter.copy(), hint);
      }
      return otherHeap;
   }
   
   public LinkedHeap<T> deleteMin()
   {
      LinkCell<LinkedHeap<T>> prevCell = new LinkCell<LinkedHeap<T>>();
      LinkedHeap<T> new_head = findPrevMin(prevCell);
      LinkedHeap<T> prev = prevCell.ptr;
      
      if (prev != null)
      {
         LinkedHeap<T> offender = prev.next();

         prev.next(offender.next()); // next could be null but so what

         if (offender.child() != null)
         {
            return spliceIn(new_head, offender.child());
         }
         return new_head;
      }
      
      if (child() == null)
      {
         if (next() == null)
         {
            return null;
         }
         return next();
      }

      if (next() == null)
      {
         LinkedHeap<T> child_neib = child().next();
         new_head = child().copy();

         if (child_neib == null)
         {
            return new_head;
         }

         return spliceIn(new_head, child_neib);
      }

      LinkedHeap<T> new_heap = next();
      return spliceIn(new_heap, child());
   }

       //////////////////////////////
   ////////// HELPERS FOLLOW ///////////
      //////////////////////////////
   
   private LinkedHeap<T> link(LinkedHeap<T> new_entry)
   {
      new_entry.next(this);
      return new_entry;
   }
   
   private LinkedHeap<T> link(LinkedHeap<T> new_entry,
                              LinkedHeap<T> neib)
   {
      LinkedHeap<T> head_copy  = this.copy();
      LinkedHeap<T> neib_copy  = neib.copy();
      
      if (neib.lt(this) && neib.lt(new_entry))
      {
         neib_copy.next(neib.next());
         neib_copy.incr();
         neib_copy.child(head_copy);
         
         head_copy.treeSib(new_entry);
         new_entry.treeSib(neib.child());

         return neib_copy;
      }
      
      if(this.lt(new_entry))
      {
         head_copy.next(neib.next());
         head_copy.incr();
         head_copy.child(neib_copy);
         
         neib_copy.treeSib(new_entry);
         new_entry.treeSib(this.child());
         
         return head_copy;
      }
         
      new_entry.next(neib.next());
      new_entry.rank(neib.rank + 1);
      new_entry.child(head_copy);
      
      head_copy.treeSib(neib_copy);

      return new_entry;
   }
   
   private LinkedHeap<T> spliceIn(LinkedHeap<T> newHeap,
                          final LinkedHeap<T> childList)
   {
      LinkedHeap<T> reversedChildren = null; // for efficient meld
      
      for (LinkedHeap<T> iter = childList; iter != null; iter = iter.next())
      {
         if (iter.rank == 0)
         {
            newHeap = newHeap.insert(iter.value);
         }
         else
         {
            // so reverse list instead and call meld
            LinkedHeap<T> entry = iter.copy();
            entry.next(reversedChildren);
            reversedChildren = entry;
         }
      }
      return newHeap.meld(reversedChildren);
   }
   
   /// warning: doesn't link up to next, by design (don't always want to)
   private LinkedHeap(LinkedHeap<T> linkedHeap)
   {
      value(linkedHeap.value);
      child(linkedHeap.child());
      rank(linkedHeap.rank);
   }
   
   /// warning: doesn't link up to next()
   private LinkedHeap<T> copy()
   {
      return new LinkedHeap<T>(this);
   }

   private void value(T entry)
   {
      value = entry;
   }
   
   private void rank(int r)
   {
      rank = r;
   }
   
   private void incr()
   {
      rank += 1;
   }
   
   private void next(LinkedHeap<T> new_sib)
   {
      sib.ptr = new_sib;
   }
   
   private void child(LinkedHeap<T> new_child)
   {
      child.ptr = new_child;
   }
   
   private void treeSib(LinkedHeap<T> new_sib)
   {
      sib.ptr = new_sib;
   }
   
   private LinkedHeap<T> next()
   {
      return sib.ptr;
   }
   
   private LinkedHeap<T> child()
   {
      return child.ptr;
   }
   
   private boolean lt(LinkedHeap<T> rhs)
   {
      return value.compareTo(rhs.value) < 0;
   }
   
   private LinkedHeap<T> findPrevMin(LinkCell<LinkedHeap<T>> prevCell)
   {
      // traverse all the way before building node copies
      LinkedHeap<T> min = findMin();

      if (min == this)
      {
         return this;
      }

      LinkedHeap<T> new_head = copy();
      LinkedHeap<T> prev = new_head;

      LinkedHeap<T> current = null;
      for (current = next(); current != min; current=current.next())
      {
         LinkedHeap<T> iter_copy = current.copy();
         prev.next(iter_copy);
         prev = iter_copy;
      }
      prev.next(current);
      prevCell.ptr = prev;
      return new_head;
   }
   
   // inserts one tree at a time into a forest.  hint is used to report one
   // before insert happened so that we get the right runtime with meld()
   private LinkedHeap<T> meldOne(LinkedHeap<T> new_root,
                                         LinkCell<LinkedHeap<T>> hint)
   {
      LinkedHeap<T> new_head = null;
      LinkedHeap<T> prev = null;

      if (hint.ptr == null)
      {
         if (new_root.rank < rank)
         {
            new_root.next(this);
            hint.ptr = new_root;
            return new_root;
         }

         // case that ranks are equal should be skipable at beginning of list since two nodes
         // of same rank ok at beginning of list.  insert will fix.

         new_head = copy();
         hint.ptr = new_head;
         hint.ptr.next(next());
         prev = new_head;
      }
      else // continuing.  copy already made.  can be destructive
      {
         new_head = this;
         prev = hint.ptr;
      }

      for (LinkedHeap<T> iter = hint.ptr.next(); iter != null; iter = iter.next())
      {
         hint.ptr = prev;
         if (new_root.rank < iter.rank)
         {
            prev.next(new_root);
            new_root.next(iter);
            return new_head;
         }
         LinkedHeap<T> iter_copy = iter.copy();

         if (iter_copy.rank == new_root.rank)
         {
            if (iter_copy.lt(new_root))
            {
               iter_copy.incr();
               iter_copy.child(new_root);
               new_root.treeSib(iter.child());

               if (iter.next() == null || iter.next().rank > iter_copy.rank)
               {
                  iter_copy.next(iter.next());
                  prev.next(iter_copy);
                  return new_head;
               }

               // ripple carry
               new_root = iter_copy;
            }
            else
            {
               new_root.incr();
               iter_copy.treeSib(new_root.child());
               new_root.child(iter_copy);

               if (iter.next() == null || iter.next().rank > new_root.rank)
               {
                  new_root.next(iter.next());
                  prev.next(new_root);
                  return new_head;
               }

               //ripple carry.  don't connect prev, yet
            }
         }
         else
         {
            prev.next(iter_copy);
            prev = iter_copy;
         }
      }
      prev.next(new_root);
      return new_head;
   }
   
   ///////////// main /////////////////
   
   public static void main(String[] args)
   {
      Random randgen = new Random(System.currentTimeMillis());
//      Random randgen = new Random(4);
      
      int total = 200000;
      ArrayList<Integer> ints = new ArrayList<Integer>(total);
      
      System.out.println("\t\t\t" + System.currentTimeMillis());
      for (int i = 0; i < total; ++i)
      {
         Integer newInt = randgen.nextInt(1000000);
//         System.out.println(newInt);
         ints.add(newInt);
      }
      System.out.println("array insert done:\t" + System.currentTimeMillis());
      
      LinkedHeap<Integer> myHeap = new LinkedHeap<Integer>(ints.get(0));
      
      for (int i = 1; i < total; ++i)
      {
         myHeap = myHeap.insert(ints.get(i));
      }
      System.out.println("heap insert done:\t" + System.currentTimeMillis());

      
      Integer prev = myHeap.findMin().value;
      Integer curr = prev;

      System.out.println("-------");
      
      int i = 1;
      while (myHeap != null)
      {
         curr = myHeap.findMin().value;
//         System.out.println(i + " " + curr);
         i+=1;
         if (prev > curr)
         {
            throw new IllegalStateException("order constraint violation");

         }
         myHeap = myHeap.deleteMin();
         prev = curr;
      }
      if (i < total)
      {
         throw new IllegalStateException("some values lost: " + i + " < " + total);

      }
      System.out.println("ok:\t\t\t" + System.currentTimeMillis());
      Collections.sort(ints);
      System.out.println("destrictive sort done:\t" + System.currentTimeMillis());
   }

//   public int compareTo(LinkedHeap<T> other)
//   {
//      return value.compareTo(other.value);
//   }
}